FIG. 1 depicts a schematic diagram of a portion of a typical wireless communications system in the prior art. Such a system provides wireless telecommunications service to a number of wireless terminals (e.g., wireless terminals 101-1 through 103-1) that are situated within a geographic region.
The heart of a typical wireless telecommunications system is Wireless Switching Center ("WSC")120, which may also be known as a Mobile Switching Center ("MSC") or a Mobile Telephone Switching Office ("MTSO"). Typically, WSC 120 is connected to a plurality of base stations (e.g., base stations 103-1 through 103-5) that are dispersed throughout the geographic area serviced by the system. Additionally, WSC 120 is connected to local- and toll-offices (e.g., local-office 130, local-office 138 and toll-office 140). WSC 120 is responsible for, among other things, establishing and maintaining calls between wireless terminals and between a wireless terminal and a wireline terminal, which is connected to the system via the local and/or long-distance networks.
The geographic area serviced by a wireless telecommunications system is partitioned into a number of spatially-distinct areas called "cells." As depicted in FIG. 1, each cell is schematically represented by a hexagon; in practice, however, each cell usually has an irregular shape that depends on terrain topography. Typically, each cell contains a base station, which comprises radios and antennas that the base station uses to communicate with the wireless terminals in that cell and also comprises the transmission equipment that the base station uses to communicate with WSC 120.
As an example of wireless telecommunications, when wireless terminal 101-1 desires to communicate with wireless terminal 101-2, wireless terminal 101-1 transmits the desired information to base station 103-1, which relays the information to WSC 120. Upon receiving the information, and with the knowledge that it is intended for wireless terminal 101-2, WSC 120 then returns the information to base station 103-1, which relays the information, via radio, to wireless terminal 101-2.
The wireless communications described above occur over a plurality of communications channels. Such channels are characterized by a carrier frequency, and a bandwidth (e.g., 30 kHz) over which the carrier frequency is modulated to carry information content. Wireless service providers license, at a very substantial cost, a band of frequency spectrum sufficient to provide an adequate number of communication channels for supporting communications within a given wireless system.
The amount of spectrum that a provider must obtain to support such communications is predominantly a function of (1) the amount of spectrum that a channel consumes, (2) the extent to which channels used in any one of the cells can be reused in other cells, (3) the traffic demand on the system, and (4) the acceptable percentage of blocked call attempts. Regarding (2), channel reuse is limited by channel interference. Such interference, which may occur between cells ("co-channel interference") and between numerically-consecutive or nearly-consecutive carrier frequencies ("adjacent-channel interference"), must be kept within acceptable limits.
Since spectrum is very expensive, it is disadvantageous for a provider to license substantially more spectrum than is required for supporting communications within its wireless telecommunications system. As such, it would be advantageous to have an efficient method for allocating spectrum (i.e., assigning channels to each cell in the system) to minimize system-wide channel requirements.
One class of allocation method is referred to as dynamic channel allocation ("DCA"). DCA schemes usually have a local focus wherein changes in call demand between nearby cells, perhaps at a number of locations throughout a wireless telecommunications system, provide the basis for a revised channel allocation that is provided by a DCA model. Such models may be used to reallocate channels on an up-to-the-minute basis. While the prior art provides a variety of DCA schemes, as a class they typically suffer from several drawbacks, as described below.
First, typical DCA models may be less reliable when used to reallocate channels as a result of relatively larger changes in call demand, such as may occur hourly (i.e., "rush" hour versus off-peak hours), daily (i.e., Monday-Friday versus the weekend), or seasonally. Second, such DCA methods are not necessarily efficient from the point of view of channel allocation on a system-wide basis. Provided with a first estimate, perhaps from a characteristic frequency reuse pattern, a DCA method is used to "fine tune" the system. To the extent that the original estimate does not efficiently allocate channels, the DCA will usually not improve allocation efficiency because of its local rather than global focus.
Thus, it would be advantageous to have a channel allocation method that is efficient regardless of the extent of system perturbations and does not depend upon the efficiency of an initial channel allocation estimate.